The present invention relates generally to computing systems and more specifically to methods and apparatus for routing data.
Routers are machines that facilitate the movement of data from a source to a destination in a reliable manner. Routers perform two fundamental functions, determine routing information for moving data packets along a route to a destination, and forward the data packets using the routing information to a next hop along the route toward the destination. The data packet forwarding process can include moving packets of data from a router input interface, through a switch fabric, to an appropriate router output interface, based on the routing information.
In some router implementations, a switch fabric includes a common memory buffer for storing the data portion of packets while the header portion is processed by routing software to determine a next hop toward the destination. Often, routers have a number of input interfaces receiving data at different rates and competing for the availability of a common output. In such devices, the memory buffer in the switch fabric is divided into a number of data input queues, each receiving data from a different input interface at a different rate.
When a number of input queues receiving data at different rates are vying for access to an output of limited bandwidth, it is important to properly manage each queue""s ability to access and monopolize the output. If a input data queue in the memory buffer is not able to access the output frequently enough, the input data queue will fill, be unable to accept new data for forwarding, and a traffic pile-up will result in those segments of the network which are forwarding data to its associated input. Similarly, if an input data queue is permitted to access the output too frequently, the input data queue will under-utilize the buffering capability of the router, and over-utilize the output interface at the expense of the other data input queues.
What is needed is an efficient method for dividing output bandwidth among a number of data input queues receiving data from a number of input devices at different data rates, such that no one input queue under-utilizes or over-utilizes the output.
In one aspect, the invention comprises a method for dividing output bandwidth among a number of data input queues receiving data from a number of input devices at different data rates. In one aspect, the invention includes a method for dividing the bandwidth of an output network line interface among a number of data input queues receiving data from a number of input network line interfaces implementing different network services and receiving data at different rates.
The output bandwidth is divided by initially assigning a priority indicator to each input queue and periodically incrementing the assigned priority indicator by a programmable weight that is proportional to the sum of the weights of all of the queues. The input queue with the highest priority indicator is generally the queue selected to transmit data to the output. However, if the queue is delineated as being rate capped, the queue will not be selected to transmit to the output though it has the highest priority indicator. The queue may not be selected whenever its priority indicator has a value that is less than an initially assigned value. Finally, whenever a byte of data is transmitted out of a queue its priority indicator is decremented.
When a queue""s priority indicator reaches a maximum allowable credit, the priority indicator is reset to the higher of the queue""s initial credit allocation or the highest priority indicator associated with the other data input queues. Similarly, when a queue""s priority indicator reaches a minimum allowable credit, it is reset to the lower of the queue""s initial credit allocation or the lowest priority indicator associated with the other data input queues.
In another aspect, the invention provides a method for distributing data transmission from a plurality of data input queues in a memory buffer to an output. The method includes associating a priority indicator with each data input queue, determining a priority indicator having a highest priority level among the plurality of priority indicators and selecting the data input queue associated with the priority indicator having the highest priority level to transmit to the output.
Aspects of the invention can include one or more of the following features. The step of associating a priority indicator with a data input queue can include setting the priority indicator to an initial priority level. The method can include determining an increment level for a data input queue. The increment level can be proportional to the output bandwidth to which the data input queue requires access. The method can include periodically increasing the priority indicator associated with the data input queue by the increment level.
The step of increasing a priority indicator can include limiting the priority indicator to a value less than a maximum priority level. The step of limiting a priority indicator to a value less than a maximum priority level can include detecting an overflow condition indicating that a priority indicator has a value greater than the maximum priority level, selecting a highest priority level among the priority indicators which is less than the maximum priority level and setting the priority level of the overflowed priority indicator to the larger of the indicator""s initial priority level and the maximum priority level.
The step of selecting a data input queue to transmit to the output can include detecting a transmit condition indicating data is being transmitted from the selected data input queue to the output and decrementing the data input queue""s priority indicator by an amount of data transmitted. The step of decrementing a priority indicator can include limiting the priority indicator to a value greater than a minimum priority level. The step of limiting a priority indicator to a value greater than a minimum priority can include detecting an underflow condition indicating that a priority indicator has a value less than a minimum priority level, selecting a lowest priority level among the priority indicators which is greater than the minimum priority level and setting the priority level of the underflowed priority indicator to the smaller of the indicator""s initial priority level and the minimum priority level.
The method can include associating a rate cap flag with a data input queue and setting the rate cap flag to indicate that the data input queue is to be rate-capped. The step of selecting a data input queue to access the output can include determining whether a rate cap flag associated with a selected data input queue is set, determining whether the priority indicator associated with the selected queue has a value less than the queue""s initial priority level and selecting another data input queue to transmit to the output.